洛谷 3594 [POI2015]WIL-Wilcze doły

发表于 | 更新于 | 阅读次数：
本文字数： 990 字 | 阅读时长 ≈ 4 分钟

最喜欢POI的题目了poi！（注意两个POI含义的区别，不懂百度）

题意简述

给定一个长度为n的序列，你有一次机会选中一段连续的长度不超过d的区间，将里面所有数字全部修改为0。请找到最长的一段连续区间，使得该区间内所有数字之和不超过p。

同样是蒯的
能蒯，为什么要自己写

思路

分析几个性质。

  1. 当右端点往右移的时候，左端点不会往左。因为我们发现，$w_i$都是正的。所以在右移的时候，和会变大，如果左端点能往左，那么我右端点在右移之前的时候，为什么不能再往左一点呢？所以，这就有了单调性（这单调性的关键就在于$w_i$是正的）

  2. 如果要我们把连续的$d$个位置删掉，那么我们肯定会删和最大的一段。

那么此时我们就有了一个初步的思路：枚举右端点，然后记录上一次的左端点，从这个记录的值开始检查一段区间是否合法。

珂是我们如何检查这段区间是否合法呢？我们发现这个东西珂以用单调队列优化。维护前缀和，设$t[i]$表示从$i$往前$d$个数的和。然后维护一个单调队列，维护的方式：

  1. 考虑到我们要求最大的和，令单调队列中的$t[i]$值单调递减（那么队列的头就是最大值了）。

  2. 当然，也要去掉一些不合法的区间。如果区间的左端点在上一次的左端点前面，那么就不满足性质2.，也就是不满足单调性，肯定是不合法的答案，舍弃。

  3. 接着就检查是否清除掉最大能清除的区间后，和$\le p$。如果这个不满足，也要舍弃掉答案。在维护3.的时候不要忘了维护2.

然后就能得到最长的区间长度了，更新答案即珂。

对单调队列不是很熟悉，讲的不好的话，珂以看看别的奆佬的博客哦~

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
// luogu-judger-enable-o2
#include<bits/stdc++.h>
using namespace std;
namespace Flandle_Scarlet
{
    #define N 2123456
    #define int long long

    #define F(i,l,r) for(int i=l;i<=r;++i)
    #define D(i,r,l) for(int i=r;i>=l;--i)
    #define Fs(i,l,r,c) for(int i=l;i<=r;c)
    #define Ds(i,r,l,c) for(int i=r;i>=l;c)
    #define Tra(i,u) for(int i=G.Start(u);~i;i=G.Next(i))
    #define MEM(x,a) memset(x,a,sizeof(x))
    #define FK(x) MEM(x,0)
    int n,p,d;
    int a[N];
    void R1(int &x)
    {
        x=0;char c=getchar();int f=1;
        while(c<'0' or c>'9') f=(c=='-')?-1:1,c=getchar();
        while(c>='0' and c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
        x=(f==1)?x:-x;
    }
    void Input()
    {
        R1(n);R1(p);R1(d);
        F(i,1,n) R1(a[i]);
    }

    int s[N],t[N];
    int Q[N];int head,tail;

    void Soviet()
    {
        F(i,1,n)
        {
            s[i]=s[i-1]+a[i];
            if (i>=d) t[i]=s[i]-s[i-d];
        }

        head=tail=1;
        int ans=d;
        Q[tail++]=d;
        int last=1;//注意，[1,d]也是一个解（绝对是的，和为0）
        F(i,d+1,n)//枚举右端点
        {
            while(head<tail and t[Q[tail-1]]<t[i]) --tail;
            Q[tail++]=i;
            //维护第1部分：区间和单调递减

            while(head<tail and Q[head]-d+1<last) ++head;
            //维护第2部分：满足单调性质2. 

            while(head<tail and s[i]-s[last-1]-t[Q[head]]>p)//计算清楚之后的和
            {
                ++last;
                while(head<tail and Q[head]-d+1<last) ++head;//不要忘了第2部分继续维护
            }
            //维护第3部分：检查清楚之后的和
            ans=max(ans,i-last+1);
            
        }
        printf("%d\n",ans);
    }
    #define FlandreScarlet void
    FlandreScarlet IsMyWife()
    {
        if (0)
        {
            freopen("","r",stdin);
            freopen("","w",stdout);
        }
        Input();
        Soviet();
    }
    #undef int //long long
};
int main()
{
    Flandle_Scarlet::IsMyWife();
    return 0;
}

w